Orthogonal transforms and transformation properties are extraordinarily useful in solving new technological problems. Such transforms permit analysis of most signals given some knowledge of its constituent parts. The Fourier transformation in particular has become a powerful tool in increasingly diverse fields including linear systems, communications systems, image processing applications, etc.
The discrete Fourier transformation (DFT) is the counterpart of the Fourier transformation in the discrete time domain. In general, the DFT may be defined as follows:                                           X            ⁡                          (              k              )                                =                                    ∑                              n                =                0                                            N                -                1                                      ⁢                                                  ⁢                                          x                ⁡                                  (                  n                  )                                            ⁢                              W                N                kn                                                    ,                                  ⁢                  k          =          0                ,        1        ,        …        ⁢                                  ,                  N          -          1                                    (        1        )            
and the inverse DFT (IDFT) is expressed as:                                           x            ⁡                          (              n              )                                =                                                    1                N                            ⁢                                                ∑                                      k                    =                    0                                                        N                    -                    1                                                  ⁢                                                                  ⁢                                                      X                    ⁡                                          (                      k                      )                                                        ⁢                                      W                    N                                          -                      kn                                                        ⁢                                                                          ⁢                  n                                                      =            0                          ,        1        ,        …        ⁢                                  ,                  N          -          1                                    (        2        )                                          where          ⁢                                          ⁢                      W            n                          =                  ⅇ                                    -              j                        ⁢                                                  ⁢            2            ⁢                                                  ⁢                          π              /              N                                                          (        3        )            
In equations (1) and (2), N is the amount of the sample, x(n) is the sample value in the time domain, and X(k) is the sample value in the frequency domain.
Direct calculation of the DFT and the IDFT is complex. It requires N2 multiplications and N(N−1) additions. Such computational may reduce signal processing speed, increased power consumption, and higher expense. One important tool in modern digital signal processing applications that helps to reduce that overhead is the Fast Fourier Transformation (FFT). By introducing the concept of divide-and-conquer, both the numbers of multiplication and addition are reduced to Nlog2N
In Discrete Multitone (DMT)-based ADSL system, a 512-point IFFT/FFT module is required to perform the modulation/demodulation kernel. At the transmitter side of the DMT system, to ensure the IFFT generates only real-valued outputs, the inputs of the IFFT have the constraintX(k)=X*(2N−k) for k=0, 1, . . . , N−1  (4)where N=256 andX(k)≡Xr(k)+j·Xi(k)  (5)are encoded complex symbols with X(0)=X(N)=0. Here, Xr(k) and Xi(k) indicate the real part and imaginary part of X(k) respectively. As defined                                           x            ⁡                          (              n              )                                =                                                    1                                  2                  ⁢                  N                                            ⁢                                                ∑                                      k                    =                    0                                                                              2                      ⁢                      N                                        -                    1                                                  ⁢                                                                  ⁢                                                      X                    ⁡                                          (                      k                      )                                                        ⁢                                      W                                          2                      ⁢                      N                                                              -                      kn                                                        ⁢                                                                          ⁢                  for                  ⁢                                                                          ⁢                  n                                                      =            0                          ,        1        ,        …        ⁢                                  ,                  N          -          1                                    (        6        )            in equation (2), the IDFT of a 2N samples sequence is where, in accordance with the equation (3)                                           W                          2              ⁢              N                                      -              nk                                ≡                      ⅇ                          j              ⁢                                                          ⁢              2              ⁢              π              ⁢                                                          ⁢                              nk                /                2                            ⁢              N                                      =                              cos            ⁢                                          2                ⁢                π                ⁢                                                                  ⁢                nk                                            2                ⁢                N                                              +                      j            ⁢                                                  ⁢            sin            ⁢                                          2                ⁢                π                ⁢                                                                  ⁢                nk                                            2                ⁢                N                                                                        (        7        )            
In accordance with U.S. Pat. No. 6,157,938, the equation (6) is decomposed by the first half and the second half by decomposing the index k, and using the facts that X(0)=X(N)=0. Therefore, the equation (6) becomes                               x          ⁡                      (            n            )                          =                              1                          2              ⁢              N                                ⁡                      [                                                            ∑                                      k                    =                    0                                                        N                    -                    1                                                  ⁢                                                                  ⁢                                                      X                    ⁡                                          (                      k                      )                                                        ⁢                                      W                                          2                      ⁢                      N                                                              -                      kn                                                                                  +                                                ∑                                      k                    =                    N                                                                              2                      ⁢                      N                                        -                    1                                                  ⁢                                                                  ⁢                                                      X                    ⁡                                          (                      k                      )                                                        ⁢                                      W                                          2                      ⁢                      N                                                              -                      nk                                                                                            ]                                              (        8        )            
Next, by applying the constraint of equation (4) and substituting equations (5) and (7) into (8), we can simplify equation (9) as follows:                                                                                           x                  ⁡                                      (                    n                    )                                                  ⁢                                =                                                      1                                          2                      ⁢                      N                                                        ·                                      2                    ⁡                                          [                                                                                                    ∑                                                          k                              =                              0                                                                                      N                              -                              1                                                                                ⁢                                                                                                          ⁢                                                                                                                    X                                r                                                            ⁡                                                              (                                k                                )                                                                                      ⁢                            cos                            ⁢                                                                                          2                                ⁢                                π                                ⁢                                                                                                                                  ⁢                                nk                                                                                            2                                ⁢                                N                                                                                                                                    -                                                                              ∑                                                          k                              =                              0                                                                                      N                              -                              1                                                                                ⁢                                                                                                          ⁢                                                                                                                    X                                i                                                            ⁡                                                              (                                k                                )                                                                                      ⁢                            sin                            ⁢                                                                                          2                                ⁢                                π                                ⁢                                                                                                                                  ⁢                                nk                                                                                            2                                ⁢                                N                                                                                                                                                        ]                                                                                                                                                              ⁢                                  =                                                            1                      N                                        ⁡                                          [                                                                                                    MDCT                            r                                                    ⁡                                                      (                            n                            )                                                                          -                                                                              MDST                            i                                                    ⁡                                                      (                            n                            )                                                                                              ]                                                                                                          ⁢                                  ⁢                                            for              ⁢                                                          ⁢              n                        =            0                    ,          1          ,          …          ⁢                                          ,                                    2              ⁢              N                        -            1                                              (        9        )                                Where        ,                                                                                                MDCT              r                        ⁡                          (              n              )                                =                                    ∑                              k                =                0                                            N                -                1                                      ⁢                                                  ⁢                                                            X                  r                                ⁡                                  (                  k                  )                                            ⁢              cos              ⁢                                                2                  ⁢                  π                  ⁢                                                                          ⁢                  nk                                                  2                  ⁢                  N                                                                    ⁢                                  ⁢                                            MDST              i                        ⁡                          (              n              )                                =                                    ∑                              k                =                0                                            N                -                1                                      ⁢                                                  ⁢                                                            X                  i                                ⁡                                  (                  k                  )                                            ⁢              sin              ⁢                                                2                  ⁢                  π                  ⁢                                                                          ⁢                  nk                                                  2                  ⁢                  N                                                                                        (        10        )            
The equation (9) Fourier Transformation calculation includes two parts, the first term is Modified Discrete Cosine Transformation (MDCT) and the second term is Modified Discrete Sine Transformation (MDST). We use subscripts r and i to indicate that the operations are performed on the real and imaginary parts of input symbol X(k), respectively. Note that the MDCTr(n) and MDSTi(n) involve only real-valued operators. Furthermore, from equation (10) it can be shown that                                                         MDCT              r                        ⁡                          (              n              )                                =                                    MDCT              r                        ⁡                          (                                                2                  ⁢                  N                                -                n                            )                                      ⁢                                  ⁢                                                            MDST                i                            ⁡                              (                n                )                                      =                                                            -                                                            MDST                      i                                        ⁡                                          (                                                                        2                          ⁢                          N                                                -                        n                                            )                                                                      ⁢                                                                  ⁢                for                ⁢                                                                  ⁢                n                            =              0                                ,          1          ,          …          ⁢                                          ,                                    2              ⁢              N                        -            1                                              (        11        )            
Consequently, calculation of equation (9) can be focused on the calculations of MDCTr(n) function and MDSTi(n) function for n=0, 1, . . . , N−1. Then the calculations of the MDCTr(n) function and the MDSTi(n) function for n=N+1, . . . , 2N−1 are expanded based upon equation (11). In this manner, this simple relationship can save an additional 50% hardware/software complexity.
In U.S. Pat. No. 6,157,938, a time-recursive FFT architecture is provided. The modulation kernels of equation (9) are mapped to the VLSI architectures based on time-recursive lattice structure as shown in FIG. 1. As the shown of the FIG. 1, the input data are separated into two phases, the real parts Xr(k) and the imaginary parts Xi(k) where k=0, 1, . . . , N−1. The real parts Xr(k), first phase, are first fed to the module. After N iterations, the MDCTr(n) is obtained at upper output. The imaginary parts Xi(k), second phase, are then fed to the lattice. Similarly, after N iterations, the MDSTi(n) is obtained at lower output. Then, the MDCTr(n) and the MDSTi(n) are combined together to obtain the IFFT answer of a 2N samples sequence by the accumulators in post-processing circuit. The overall architecture disclosed by U.S. Pat. No. 6,157,938 is illustrated in the FIG. 2.
However, in FIG. 2, the input data are decomposed into real part Xr(k) and imaginary part Xi(k) and they are fed into the modules in two different phases. The real part Xr(k) and imaginary part Xi(k) respectively require N iterations to get the MDCTr(n) and the MDSTi(n). Namely, 2N iterations are required to obtain the final results x(n), which results in extra N-cycle latency in practical implementations. Thus, there is an ongoing need to reduce the number of IFFT computations, and in particular the number of complex multiplications, that must be performed in order to more efficiently compute the IFFT.